Basic information

• t-SNE: t-distributed stochastic neighbor embedding

• Method for visualizing high-dimensional data by giving each datapoint a location in a two or three-dimensional map

• Computational complexity of direct implementation: \(O(N^{2})\)

• Original paper - Laurens van der Maaten, Geoffrey Hinton, 2008

T-sne is based on Stochastic Neighbor Embedding originally developed by Sam Roweis and Geoffrey Hinton, where Laurens van der Maaten proposed the t-distributed variant. It is a nonlinear dimensionality reduction technique well-suited for embedding high-dimensional data for visualization in a low-dimensional space of two or three dimensions. Specifically, it models each high-dimensional object by a two- or three-dimensional point in such a way that similar objects are modeled by nearby points and dissimilar objects are modeled by distant points with high probability.

Example data

Let’s assume that we have 5 datapoints (“A”, “B”, “C”, “D”, “E”) embedded in 3-dimensional space. Our objective is to embed these points in the 2-dimensional space so that the local structure is preserved.

Step 1 - calculation of distances between the points

Firstly, let’s calculate the eucliadean distances between the points in the high-dimensional space, i.e.:

\[ d(x,y) = \sqrt{ \sum_{i=1}^{n} (x_{i} - y_{i})^{2} }\]

Step 2 - calculation of probability distribution in high-dim space

For each point(!) in our dataset we shall calculate the similarity to other datapoints, which is described in the original paper as follows: similarity of datapoint \(x_{j}\) to datapoint \(x_{i}\) is the conditional probability \(p_{j|i}\) that \(x_{i}\) would pick \(x_{j}\) as its neighbor. Note that definition is not symmetric, i.e. \(p_{j|i} \neq p_{i|j}\).

Let’s pick one point, e.g. “A” and calculate the aforementioned conditional probabilities with respect to point “A”:

We map the distances to the Gaussian distribution with mean = 0. The probabilities that point “A” will pick the point “B” as its neighbor is equal to the value of density of normal distribution \((0, \sigma_{A})\) in point “Dist A-B”:

Additionally, we assume that \(p_{i|i} = 0\) by definition. After we calculate the densities for all points, we normalize the values in order to have the probability distribution. Overall, the probability that point \(i\) will pick point \(j\) is given by the formula:

\[ p_{j|i} := \frac{exp(-|| x_{i} - x_{j} ||^{2} /2 \sigma_{i}^{2} )}{\sum_{k \neq i} exp(-|| x_{i} - x_{k} ||^{2} /2 \sigma_{i}^{2} )} \]

The remaining issue is the algorithm of determining the sigma values in the normal distribution (c.f. Appendix 1).

Now, we have the similarity of datapoint “A” to other datapoints defined as the conditional probability \(p_{A|X}\) (\(A\) would pick \(X\) as it neighbor):

\(P_{A}:\)
\(p_{B|A} = 0.302\)
\(p_{C|A} = 0.282\)
\(p_{D|A} = 0.189\)
\(p_{E|A} = 0.226\)

Let’s calculate all 5 distributions (one distribition per one datapoint):

Step 3 - calculation of probability distribution in low-dim space

Let’s do exactly the same thing in low-dimensional space by performing the following steps:

• we randomly(!) select the coordinates of all datapoints in low-dimensional space
• instead of normal distribution we apply t-student distribution

Overall, the probability, that point i will pick point j is given by the formula:

\[ q_{j|i} := \frac{exp(-|| x_{i} - x_{j} ||^{2} /2 )}{\sum_{k \neq i} exp(-|| x_{i} - x_{k} ||^{2} )} \]

Step 4 - training of supervised model

Now, for each point we have two distributions: in low-dim space (Q) and high-dim space (P).

Now, the idea is to change to coordinates in low-dim space so that the \(Q_{i}\) distributions are similar to the \(P_{i}\) ones so that we can reflect the local structures of high-dim space in low-dim space. Effectively, we tackle the problem of finding optimizing the parameters (just like in supervised model):

• Parameters to be trained: coordinates of points in low-dimensional space
• Actual values: P-distributions
• Optimizer: stochastic gradient descent
• Loss function: Kullback–Leibler divergence:

\[ D_{KL} (P || Q) = \sum_{x \in X} P(x) \cdot log_{2}\frac{P(x)}{Q(x)} \]

or, using the previous notations (for point A):

\[ D_{KL} (P || Q) = \sum_{j \in \{B, C, D, E \}} p_{j|A} \cdot log_{2}\frac{p_{j|A}}{q_{j|A}} \]

For all points in the dataset:

\[ D_{KL} (P || Q) = \sum_{i \in \{A, B, C, D, E \}} \sum_{j \in \{A, B, C, D, E \}} p_{j|i} \cdot log_{2}\frac{p_{j|i}}{q_{j|i}} \]

In practise, we can also define \(p_{ij}:=\frac{p_{j|i} + p_{i|j}}{2n}\) and change the loss function to the folowing form:

\[ D_{KL} (P || Q) = \sum_{i \in \{A, B, C, D, E \}} \sum_{j \in \{A, B, C, D, E \}} p_{ji} \cdot log_{2}\frac{p_{ji}}{q_{ji}}, \]

where \(p_{ij} = p_{ji}\) and \(q_{ij} = q_{ji}\).

Final output

From technical reasons the original dataset was extended by adding some noise.

The results in 2-dim space are the following:

Examples

Appendix